#include <iostream>
#include <vector>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

TreeNode *dfs(vector<int> &preorder, vector<int> &inorder, int l1, int r1, int l2, int r2)
{
    if (l1 > r1)
        return nullptr;
    int midVal = preorder[l1];
    printf("midVal = %d\n", midVal);
    int inorderIndex = l2;
    for (int i = l2; i <= r2; i++)
    {
        if (midVal == inorder[i])
        {
            inorderIndex = i;
            printf("inorderIndex = %d\n", inorderIndex);
        }
    }
    int numleft = inorderIndex - l2;
    TreeNode *root = new TreeNode(midVal);
    root->left = dfs(preorder, inorder, l1 + 1, l1 + numleft, l2, inorderIndex - 1);
    root->right = dfs(preorder, inorder, l1 + numleft + 1, r1, inorderIndex + 1, r2);
    return root;
}

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder)
{
    TreeNode *root = dfs(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    return root;
}

int main()
{
    vector<int> preorder = {3, 9, 20, 15, 7};
    vector<int> inorder = {9, 3, 15, 20, 7};
    TreeNode *root = buildTree(preorder, inorder);
}